#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <ctime>
#include <cstdio>

/*
 * 求1到1亿个素数问题
 *
 *
 * 程序的思路是用字节中的位来代表每一个整数，这样从空间上来说是最省的。
 * 
 * 100000000 / 8 = 12500000   (ps: 1亿个数用1亿个位表示)
 * 
 * 1 亿个整数只要用12500000个字节表示，按一个整数32位计算，只要12500000/4个整型数就可以表示。
 *
 * 12500000 / 4 = 3125000	  (ps: 一个int整型数占4字节（Byte），也就是32位（bit）,共需这么多个整型数内存)
 *
 * 筛法循环1亿的平方根次，即1万次，显然对于1亿以内的整数，如果它是合数，就一个定有1万以内的整数因子。
 *
 * 去掉1万以内所有数的倍数，剩下的就是素数了。
 *
 * 对于第i个整数，它所对应的32位整数序位为 i/32，它所对应的整数中的位序为 i%32。
 *
 * 判断第i个整数是否素数，可以看做判断 p[i/32] & (1 << i%32)是否为1。
 *
 * 第j个整数置为合数的操作，可以看做相应位置0
 *
 */

#if 0
/*
 * 位图（Bitmap）算法
 */

/* example: 6,3,8,25,32,36,100 */

			31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0

[0]			0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 1 0 1 0 0 1 0 0 0	// 3,6,8,25

[1]			0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 0 0 0 0 0 1 0 0 1	// 32,36

[2]			0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 0 0 0 0 0 0 0 0 0

/* 整数100对应第 100/32 = 3个无符号整数 */
[3]			0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 0 0 0 0 1 0 0 0 0	// 100.[整数100对应无符号整数的第 100%32=4 位]

[4]			0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 0 0 0 0 0 0 0 0 0
...
[3124998]	0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 0 0 0 0 0 0 0 0 0

[3124999]	0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 0 0 0 0 0 0 0 0 0

/*
 * ps : n / 32 计算所在的行, n % 32 计算所在的列
 */

#endif

int count(unsigned int a)
{
	int sum = 0; 
	unsigned int x;
	
	for (x = a; x; x >>= 1)
		if (x & 1)
			sum++;

	return sum;
}

void sieve(unsigned int * p)
{
	int i, j;

	/*
	 * 筛选取循环1亿的平方根次,即1万次,显然对于1亿以内的数,如果它是合数,就一定有1万以内的整数因子.
	 * 
	 * 去掉1万以内所有数的倍数,剩下的就是素数了.
	 *
	 * 对于第i个整数,它所对应的32位整数序位为 i / 32, 它所对应的整数中的位序为 i % 32.
	 *
	 * 判断第i个整数是否素数,可以看做判断p[i/32] & (1 << i % 32) 是否为1.
	 *
	 * 第j个整数置为合数的操作,可以看做相应位置0.
	 *
	 */
	for (i = 2; i <= 10000; ++i) {
		if (p[i / 32] & (1 << i % 32))				// 判断第i个整数是否素数，可以看做判断 p[i/32] & (1 << i%32)是否为1
			for (j = i * i; j < 100000000; j += i)
				p[j/32] &= ~(1 << j % 32);			// 第j个整数置为合数的操作，可以看做相应位置0
	}
}

int main()
{
	int i;
	int num;

	clock_t start = clock();

	unsigned int * p = (unsigned int *) malloc (12500000);
	if (!p) {
		printf("no enough memory.\n");
		return -1;
	}

	memset(p, 255, 12500000);	// 将这1亿位初始化为全1。留心memset是以字节为单位来操作的，一个全1的字节表示为255, 或者 -1。
	sieve(p);

	num = -2;
	for (i = 0; i < 12500000 / 4; ++i)	// 1亿个位对应具有32位的整数有12500000/4个。循环统计每个整数的非0位数，就是素数的个数。
		num += count(p[i]);				// 统计一个无符号整数中的非0位数，可以用循环判断整数最低位是否为1，并逐渐右移的方法，真到该整数为全0为止。

	free(p);
	//printf("%d, %7.3f\n", num, (clock() - start) / CLK_TCK);
	printf("%d, %7.3f\n", num, (double)((clock() - start) / 1000));
}

